[Java] Priority Queue

想要寫一個利用Huffman Code做的壓縮軟體，寫到一半發現需要使用Priority Queue來提升排序效能，剛好也想自己刻一個看看，於是就寫了一個陽春版本的，簡單提供幾項功能，之後再來修改程式碼和做成GUI版本。

而這個Priority Queue是利用Min-Heap做的。

Insert

插入元素，可一次插入一個以上

Remove

也就是擷取最上層最小的元素

Change

更改Value值

Empty

檢查是否為空

Show

顯示所有元素

Clear

清空

Main

package priorityqueue;

import java.util.Scanner;
import java.util.Vector;

public class Main {
	public static void main(String[] args) {
		PriorityQueue PQ = new PriorityQueue();
		String input = "";
		Vector <Integer> number = new Vector(); ;
		Scanner scanner = new Scanner(System.in);
		while( !input.equals("end") )
		{
			System.out.println("Input your operation : insert , remove , change , empty , show , clear , end ");
			input = scanner.next();
			if ( input.equals("insert"))
			{
				System.out.println("Please input the amount.") ;
				int amount = scanner.nextInt();
				if ( amount == 0 )
				{
					System.out.println("None!") ;
				}
				else if ( amount == 1 )
				{
					System.out.println("Please input your number.") ;
					int n = scanner.nextInt();
					number.clear();
					number.add(n) ;
					PQ.insert(number);
				}
				else if ( amount < 0 )
				{
					System.out.println("Error!") ;
				}
				else
				{
					System.out.println("Please input your numbers.") ;
					number.clear();
					for ( int i = 0 ; i < amount ; i ++ )
					{
						int n = scanner.nextInt();
						number.add(n) ;
					}
					PQ.insert(number);
				}

			}
			else if ( input.equals("remove"))
			{
				System.out.println("Your number is : "+PQ.remove()) ;
			}
			else if ( input.equals("change"))
			{
				System.out.println("Input the index ") ;
				int n = scanner.nextInt();
				System.out.println("Input the value ") ;
				int v = scanner.nextInt();
				if ( n >= PQ.heap.size() )
					System.out.println("Out of index") ;
				else
					PQ.change(n,v);
			}
			else if ( input.equals("empty"))
			{
				System.out.println(PQ.is_empty()) ;
			}
			else if ( input.equals("show"))
			{
				PQ.show();
			}
			else if ( input.equals("clear"))
			{
				PQ.heap.clear() ;
			}
			else if ( input.equals("end"))
			{
				break ;
			}
			else
			{
				System.out.println("Error! Please input again.") ;
			}
				
		}
	}
}

PriorityQueue

package priorityqueue;

import java.util.Vector;

public class PriorityQueue {
	
	Vector<Integer> heap = new Vector();
	public void insert(Vector<Integer> v)
	{
		for ( int i = 0 ; i < v.size() ; i ++ )
		{
			heap.add(v.get(i)) ;
		}
		for ( int i = heap.size()-v.size() ; i < heap.size() ; i ++ )
		{
			for( int j = i ; j > 0 ; j /= 2 )
			{
				int k ;
				if ( j % 2 == 0 )
				{
					k = j / 2 - 1 ;
				}
				else
				{
					k  = j / 2 ;
				}
				if ( heap.get(j) < heap.get(k) )
				{
					int temp = heap.get(j) ;
					heap.set(j,heap.get(k)) ;
					heap.set(k,temp) ;
				}
				else
				{
					break ;
				}
			}
		}
	}
	public int remove()
	{
		int n = heap.get(0) ;
		heap.set(0,heap.get(heap.size()-1)) ;
		heap.set(heap.size()-1,n) ;
		for( int i = 0 ; i < heap.size() ; )
		{
			int k = i * 2 + 1 ;
			if ( (heap.get(i) < heap.get(k) && heap.get(i) < heap.get(k+1)) || heap.size() - 1  <= k )
			{
				break ;
			}
			else if ( heap.get(k) < heap.get(k+1) || heap.size() - 1 <= k + 1  )
			{
				int temp = heap.get(i) ;
				heap.set(i,heap.get(k)) ;
				heap.set(k,temp) ;
				i = i * 2 + 1 ; 
			}
			else
			{
				int temp = heap.get(i) ;
				heap.set(i,heap.get(k+1)) ;
				heap.set(k+1,temp) ;
				i = i * 2 + 2 ; 
			}
		}
		heap.remove(heap.size()-1) ;
		return n ;
	}
	public void change(int n , int v)
	{
		heap.set(n,v) ;
		int k ;
		if ( n % 2 == 0 )
		{
			k = n / 2 - 1 ;
		}
		else
		{
			k  = n / 2 ;
		}
		if ( heap.get(n) < heap.get(k) )
		{
			for( int j = n ; j > 0 ; j /= 2 )
			{
				if ( j % 2 == 0 )
				{
					k = j / 2 - 1 ;
				}
				else
				{
					k  = j / 2 ;
				}
				if ( heap.get(j) < heap.get(k) )
				{
					int temp = heap.get(j) ;
					heap.set(j,heap.get(k)) ;
					heap.set(k,temp) ;
				}
				else
				{
					break ;
				}
			}
		}
		else
		{
			for( int i = n ; i < heap.size() ; )
			{
				k = i * 2 + 1 ;
				if (  heap.size()  <= k  )
				{
					break ;
				}
				else if (heap.get(i) < heap.get(k) && heap.get(i) < heap.get(k+1)) 
				{
					break ;
				}
				else if ( heap.size()  <= k + 1 )
				{
					int temp = heap.get(i) ;
					heap.set(i,heap.get(k)) ;
					heap.set(k,temp) ;
					i = i * 2 + 1 ; 
				}
				else if ( heap.get(k) < heap.get(k+1) )
				{
					int temp = heap.get(i) ;
					heap.set(i,heap.get(k)) ;
					heap.set(k,temp) ;
					i = i * 2 + 1 ; 
				}
				else
				{
					int temp = heap.get(i) ;
					heap.set(i,heap.get(k+1)) ;
					heap.set(k+1,temp) ;
					i = i * 2 + 2 ; 
				}
			}
		}
	}
	public boolean is_empty()
	{
		if ( heap.size() == 0 )
			return true ;
		else
			return false ;
	}
	public void show()
	{
		if ( heap.size() == 0 )
		{
			System.out.println("Empty!") ;
		}
		else
		{
			for ( int i = 0 ; i < heap.size() ; i ++ )
				System.out.print(heap.get(i)+" ");
			System.out.println();
		}
	}
	public void clear()
	{
		heap.clear();
	}
	PriorityQueue(){
	}
}